#include <iostream>  
#include <vector>  
using namespace std;  
  
// 假设的硬币重量函数  
int getRealCoinWeight(int studentID) {  
    int lastTwoDigits = studentID % 100;  
    return lastTwoDigits % 10 + 2;  
}  
  
// 递归查找假币的函数  
int findFakeCoin(vector<int>& coins, int left, int right) {  
    if (left == right) {  
        // 只剩下一枚硬币，它就是假币  
        return left;  
    }  
      
    int n = right - left + 1;  
    int third = n / 3;  
    int weightLeft = 0, weightRight = 0;  
      
    // 计算左边和右边硬币的总重量  
    for (int i = 0; i < third; ++i) {  
        weightLeft += coins[left + i];  
    }  
    for (int i = 0; i < third && left + third + i <= right; ++i) {  
        weightRight += coins[left + third + i];  
    }  
      
    if (weightLeft < weightRight) {  
        // 假币在左边三分之一的硬币中  
        return findFakeCoin(coins, left, left + third - 1);  
    } else {  
        // 假币在右边三分之二的硬币中（包括中间那份）  
        return findFakeCoin(coins, left + third, right);  
    }  
}  


// 递归查找假币的函数  
int findFakeCoin2(vector<int>& coins, int left, int right, int& steps) {  
    if (left == right) {  
        // 只剩下一个硬币，它就是假币  
        steps++;  
        cout << "Step " << steps << ": 假币是第 " << left + 1 << " 个硬币。" << endl;  
        return left;  
    }  
      
    int n = right - left + 1;  
    int third = n / 3;  
    int weightLeft = 0, weightMiddle = 0, weightRight = 0;  
      
    // 计算左边、中间和右边硬币的总重量  
    for (int i = 0; i < third; ++i) {  
        weightLeft += coins[left + i];  
    }  
    for (int i = 0; i < third && left + third + i <= right; ++i) {  
        weightMiddle += coins[left + third + i];  
    }  
    for (int i = 0; i < third && left + 2 * third + i <= right; ++i) {  
        weightRight += coins[left + 2 * third + i];  
    }  
      
    steps++;  
    cout << "Step " << steps << ": 称重硬币 " << left + 1 << " 到 " << left + third << " 与硬币 "  
         << left + third + 1 << " 到 " << left + 2 * third << endl;  
      
    if (weightLeft < weightMiddle) {  
        // 假币在左边三分之一的硬币中  
        return findFakeCoin2(coins, left, left + third - 1, steps);  
    } else if (weightMiddle < weightRight) {  
        // 假币在中间三分之一的硬币中  
        return findFakeCoin2(coins, left + third, left + 2 * third - 1, steps);  
    } else {  
        // 假币在右边三分之一的硬币中  
        return findFakeCoin2(coins, left + 2 * third, right, steps);  
    }  
}  


int main() {  
    int n;  
    int studentID;  
    cout << "请输入硬币的数量n (n > 3): ";  
    cin >> n;  
    cout << "请输入你的学号: ";  
    cin >> studentID;  
      
    // 初始化硬币重量数组，除了一个假币外都是真币重量  
    vector<int> coins(n);  
    int realWeight = getRealCoinWeight(studentID);  
    for (int i = 0; i < n; ++i) {  
        coins[i] = (i == 0) ? realWeight - 1 : realWeight;  
    }  
      
    int steps = 0; // 记录步骤数  
    int fakeCoinIndex = findFakeCoin2(coins, 0, n - 1, steps);  
      
    cout << "共需 " << steps << " 步来找到假币。" << endl;  
    return 0;  
}
  
// int main() {  
//     int n;  
//     cout << "请输入硬币的数量n (n > 3): ";  
//     cin >> n;  
      
//     int studentID;  
//     cout << "请输入你的学号: ";  
//     cin >> studentID;  
      
//     int realWeight = getRealCoinWeight(studentID);  
//     cout << "真币的重量为: " << realWeight << endl;  
      
//     vector<int> coins(n);  
//     // 初始化硬币重量，除了一个假币外都是真币重量  
//     for (int i = 0; i < n; ++i) {  
//         coins[i] = (i == 0) ? realWeight - 1 : realWeight;  
//     }  
      
//     int fakeCoinIndex = findFakeCoin(coins, 0, n - 1);  
//     cout << "假币的索引为: " << fakeCoinIndex << endl;  
      
//     return 0;  
// }